import { AStarNode } from "./AStarNode";

enum AStarState {
    /**初始化 */
    Init,
    /**搜索中 */
    Searching,
    /**结束 */
    End,
}

/**a*算法 */
export abstract class AStarAlgo {
    /**状态 */
    private state: AStarState = AStarState.Init;

    /**开放路径 */
    private openArray: AStarNode[] = [];
    /**关闭路径 */
    private closeArray: AStarNode[] = [];
    /**结束结点 */
    private endNode?: AStarNode;

    /**结果 */
    private result?: AStarNode[];

    private init(): void {
        //建立终点
        this.endNode = this.createEndNode();
        const startNode = this.createStartNode();
        startNode.G = 0;
        startNode.H = this.heuristic(startNode);
        //建立开始和结束结点
        this.openArray.push(startNode);
    }

    /**寻路 */
    public findPath(): AStarNode[] {
        //如果已经结束了
        if (this.state == AStarState.End) {
            return this.result ?? [];
        }
        //初始化阶段，进行初始化
        if (this.state == AStarState.Init) {
            this.state = AStarState.Searching;
            //初始化数据
            this.init();
        }

        /**在搜索中，怎么处理 */
        /**搜索最短结点 */
        const target: AStarNode | null = this.search();
        const path: AStarNode[] = [];
        let head = target;
        while (head) {
            path.push(head);
            head = head.parent;
        }
        //翻转数组
        path.reverse();
        //缓存结果
        this.result = path;
        //结束了
        this.state = AStarState.End;
        //途径的路径
        return path;
    }

    private search(): AStarNode | null {
        do {
            //选出最小结点
            const current = this.findMinPath();
            this.openArray.splice(this.openArray.indexOf(current), 1);
            this.closeArray.push(current);
            if (current.equal(this.endNode!)) {
                //找到了最短路径
                return current;
            }
            //从邻居结点中找最短的
            const neighbors = this.getNeighbors(current);
            neighbors.forEach(neighbor => {
                //判断关闭列表中是否已经有此结点了
                if (this.closeArray.some(node => node.equal(neighbor))) {
                    return;
                }
                //距离
                const rentativeGScore = current.G + current.realDistance(neighbor);
                //判断目标中是否已经有这个结点了
                const targetNode = this.openArray.find(node => node.equal(neighbor));
                //如果存在同样的结点,判断距离
                if (targetNode) {
                    //如果距离比原来的小
                    if (rentativeGScore < targetNode.G) {
                        //此结点的目标更新
                        targetNode.parent = current;
                        targetNode.G = rentativeGScore;
                    }
                } else {
                    //记录邻居结点
                    neighbor.parent = current;
                    neighbor.G = rentativeGScore;
                    neighbor.H = this.heuristic(neighbor);
                    //加入打开的数组
                    this.openArray.push(neighbor);
                }
            });
            //对数组进行排序
            this.openArray.sort((a, b) => a.F - b.F);
        } while (this.openArray.length > 0);
        return null;
    }

    /**建立开始结点 */
    protected abstract createStartNode(): AStarNode;

    /**建立结束结点 */
    protected abstract createEndNode(): AStarNode;

    /**
     * 找出目前开放组中预估距离最近的
     * @returns 
     */
    private findMinPath(): AStarNode {
        return this.openArray[0];
    }

    /**获取邻居结点 */
    protected abstract getNeighbors(node: AStarNode): AStarNode[];

    /**结点到终点的预期距离 */
    protected heuristic(nodeA: AStarNode): number {
        return nodeA.pos.clone().subtract(this.endNode!.pos).length();
    }
}